package day0217

func findDisappearedNumbers1(nums []int) []int {
	n := len(nums)
	t := make([]int, n+1)
	var res []int
	for _, v := range nums {
		t[v] = 1
	}
	for i := 1; i < n+1; i++ {
		if t[i] == 0 {
			res = append(res, i)
		}
	}
	return res
}

func findDisappearedNumbers(nums []int) (res []int) {
	n := len(nums)
	for i := 0; i < n; i++ {
		t := (nums[i] - 1) % n
		nums[t] += n
	}
	for i := 0; i < n; i++ {
		if nums[i] <= n {
			res = append(res, i+1)
		}
	}
	return res
}

func findDisappearedNumbers2(nums []int) (res []int) {
	n := len(nums)
	for _, v := range nums {
		t := abs(v) - 1
		nums[t] = -abs(nums[t])
	}
	for i := 0; i < n; i++ {
		if nums[i] > 0 {
			res = append(res, i+1)
		}
	}
	return res
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}
